package com.leetcode.LC_MED;

import java.util.Arrays;
import java.util.Stack;

public class LC581 {
    public int findUnsortedSubarray2(int[] nums) {

        int[] clone = nums.clone();
        Arrays.sort(nums);
        int a = 0, b = 0;
        for (int i = 0; i < clone.length; i++) {
            if (clone[i] != nums[i]) {
                a = i;
                break;
            }
        }
        for (int i = clone.length - 1; i >= 0; i--) {
            if (clone[i] != nums[i]) {
                b = i;
                break;
            }
        }
        if (b != 0) {
            return b - a + 1;
        } else {
            return 0;
        }
    }

    public int findUnsortedSubarray3(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }

/*    作者：LeetCode
    链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leetcode/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

    public int findUnsortedSubarray4(int[] nums) {

        Stack<Integer> stack = new Stack<Integer>();
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                l = Math.min(l, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                r = Math.max(r, stack.pop());
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;

/*        作者：LeetCode
        链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leetcode/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    }

    public static void main(String[] args) {
        System.out.println(new LC581().findUnsortedSubarray2(new int[]{2, 6, 8, 10, 9, 15}));
    }
}
